import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author tianzhenjiu
 * @date 2021/1/20 15:06
 */
public class RedBlackTree {


    Node tail = new Node();

    class Node {

        int val;

        boolean isRed;


        Node leftChild = tail;

        Node rightChild = tail;


        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", color=" + isRed +
                    ", leftChild=" + leftChild.val +
                    ", rightChild=" + rightChild.val +
                    '}';
        }
    }


    /**
     * 右旋
     *
     * @param head
     * @return
     */
    public Node rotateRight(Node head) {

        Node leftNode = head.leftChild;

        head.leftChild = leftNode.rightChild;

        leftNode.rightChild = head;


        return leftNode;
    }


    /**
     * 左旋
     *
     * @param head
     * @return
     */
    public Node rotateLeft(Node head) {

        Node rightNode = head.rightChild;

        head.rightChild = rightNode.leftChild;

        rightNode.leftChild = head;


        return rightNode;
    }

    /**
     *
     * 红黑树插入
     * @param head
     * @param insertVal
     * @param isLeft
     * @return
     */
    public   Node  rbInsert(Node head,int insertVal,boolean  isLeft){


        if(head == null||head==tail){

            Node node=new Node();

            node.val=insertVal;

            node.isRed=true;

            return node;
        }


        /**
         *
         * case3
         *
         * 父节点和叔节点均为红色
         *现在的父为head.leftChild,叔为head.rightChild
         *
         * 需要把 祖父节点改程红色
         * 父和叔父都黑色
         *
         * 不违反 红黑树性质4,性质5
         */
        if(head.leftChild.isRed&&head.rightChild.isRed){

            head.isRed=true;
            head.leftChild.isRed=false;
            head.rightChild.isRed=false;
        }



        if(insertVal<head.val){

            head.leftChild=rbInsert(head.leftChild,insertVal,true);


            /**
             *
             * case4
             *
             * 如果付节点与本节点链接指向不同边  需要把父节点旋转
             *
             *
             */
            if(head.isRed&&head.leftChild.isRed&&!isLeft){
                head=rotateRight(head);
            }


            /**
             * case5 如果父节点 本节点链接指向同边，需要旋转，同左就右旋，同右就左旋
             * 然后改变旋转账户父节颜色和新节点颜色
             */
            if(head.leftChild.leftChild!=null){

                if(head.leftChild.leftChild.isRed&&head.leftChild.isRed){

                    head=rotateRight(head);

                    head.isRed=false;
                    head.rightChild.isRed=true;
                }

            }

        }
        else{


            head.rightChild=rbInsert(head.rightChild,insertVal,false);

            if(head.isRed&&head.rightChild.isRed&&isLeft){
                head=rotateLeft(head);
            }


            if(head.rightChild.rightChild!=null){

                if(head.rightChild.rightChild.isRed&&head.rightChild.isRed){

                    head=rotateLeft(head);

                    head.isRed=false;
                    head.leftChild.isRed=true;
                }
            }


        }



        return head;
    }


    /**
     *
     * 辅助方法-打印红黑树
     *
     * @param head
     */
    public  void  printRbTree(Node head){

        Map<Integer,List<Node>> listMap=new HashMap<>(16);
        iteratorRbtree(head,listMap,0);


        listMap.entrySet().forEach((entry)->{

            System.out.println(entry.getKey()+"->"+entry.getValue());
        });

    }


    public  void  iteratorRbtree(Node head, Map<Integer,List<Node>> listMap,int deep){


        List<Node> nodes=null;

        if(!listMap.containsKey(deep)){
            nodes=new ArrayList<>();
            listMap.put(deep,nodes);
        }
        else{
            nodes=listMap.get(deep);
        }

        nodes.add(head);


        if(head.leftChild!=tail){
            iteratorRbtree(head.leftChild,listMap,deep +1);
        }

        if(head.rightChild!=tail){
            iteratorRbtree(head.rightChild,listMap,deep +1);
        }

    }


    public static void main(String[] args) {


        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};


        RedBlackTree tree = new RedBlackTree();

        Node head = null;

        for (int i = 0; i < 1000; i++) {
            head = tree.rbInsert(head,i,true);
            head.isRed=false;
        }

        tree.printRbTree(head);
        System.out.println(head);
    }
}
